计算机科学Sardinas–Patterson 算法本页总览Sardinas–Patterson 算法阐述 在多项式时间内判断变长码是否唯一可译的算法。 设码为 CCC，定义两个语言之间的左商为 N−1D={y∣xy∈D and x∈N}N^{-1} D=\{y \mid x y \in D \text { and } x \in N\}N−1D={y∣xy∈D and x∈N} 则计算 S1=C−1C\{ε}S_{1}=C^{-1} C \backslash\{\varepsilon\}S1=C−1C\{ε}、Si+1=C−1Si∪Si−1CS_{i+1}=C^{-1} S_{i} \cup S_{i}^{-1} CSi+1=C−1Si∪Si−1C，直到不再出现新的元素或出现与 CCC 中重复的元素为止。 实例 性质 相关内 容 参考文献 Sardinas–Patterson Algorithm